package 柱状图中最大的矩形;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/28 10:44
 * @description:
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 */
public class Solution {
    public int largestRectangleArea(int[] heights) {
        // 双指针（也可以称为DP算法）
        // 以当前柱子寻找矩形，向左右两边扩展的时候，相当于就是扩展宽度，高度是固定为当前的柱子。
        // 那么矩形最大面积就是找到左边边第一个小于该柱子的索引下标，以及右边第一个个小于该柱子高度的下标

        // 能覆盖当前柱子的最大矩形的高，受限于该柱子的高度，否则就会被别的柱子“卡住”,所以在计算面积的时候高度都是以当前柱子为准

        int size = heights.length;
        int[] leftIndex = new int[size];
        int[] rightIndex = new int[size];
        int result = heights[0];
        // 寻找左边第一个小于该柱子的索引
        leftIndex[0] = -1;   //防止while陷入死循环
        for (int i = 1; i < size; i++) {
            int j = i - 1;
            while (j >= 0 && heights[j] >= heights[i]) {
                j = leftIndex[j];
            }
            leftIndex[i] = j;
        }
        // 寻找右边第一个小于该柱子的索引
        rightIndex[size - 1] = size; // 防止while陷入死循环
        for (int i = size - 2; i >= 0; i--) {
            int j = i + 1;
            while (j < size && heights[i] <= heights[j]) {
                j = rightIndex[j];
            }
            rightIndex[i] = j;
        }
        // 判断最大值
        for (int i = 0; i < size; i++) {
            // 以当前柱子的高度进行计算
            int w = rightIndex[i] - leftIndex[i] - 1;
            int h = heights[i];
            result = Math.max(result, w * h);
    }

        return result;
    }
}